#include <stdio.h>
/*
    选择排序进阶版
    void heap(int a[],int n){
        1.build_heap;创建大根堆
        2.堆顶始终为当前堆的最大值
        3.堆顶和堆尾交换
        4.堆长-1
        5.保持堆的秩序
        6.回到3 知道堆长为1
    }
*/
/**********交换函数************/
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
/***********下移函数***********/
/*
对于长为n的堆a[]
如果需要,把第i号元素下移到正确的位置
*/
void shift_down(int a[], int n, int i)
{
    int temp = a[i];
    /*2*i+1>n的时候 为叶子节点 不需要下移*/
    while (2 * i + 1 < n)
    {
        int t = 2 * i + 1;
        /*如果i号节点有右节点,比较左右节点大小，选择大的节点*/
        if (t + 1 < n && a[t] < a[t + 1])
            t += 1;
        /*temp小于a[t](子节点),a[i]上移(覆盖)*/
        if (temp < a[t])
        {
            a[i] = a[t];
            i = t;
        }
        else
            break;
    }
    //把temp放在正确的位置
    a[i] = temp;
}
/**********创建堆************/
void build_heap(int a[], int n)
{
    /*
        从第一个非叶子开始,调整他们的位置
        保证每个节点的子节点都是正确的位置
    */
    for (int i = n / 2 - 1; i >= 0; i--)
        shift_down(a, n, i);
}
/**********堆排序************/
void heap_sort(int a[], int n)
{
    //1.
    build_heap(a, n);
    //6.堆长>1循环进行(i是数组下标开始) 4.每次堆的长度-1
    for (int i = n - 1; i > 0; i--)
    {
        //3. 交换堆顶与当前堆尾
        swap(a[0], a[i]);
        //5. 保持堆的秩序
        shift_down(a, i, 0);
    }
}
int main()
{
    /*******************code*******************/
    int a[10] = {4, 3, 8, 2, 7, 11, 6, 1, 0, 15};
    heap_sort(a, 10);
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
